In packet-switched networks, packets traveling from a source node to a destination node may be transmitted through many intermediate network nodes, such as switches or routers. Intermediate network nodes that receive packets headed for a destination node utilize lookup tables to determine the next path for the packets. The lookup tables include forwarding information that indicates the path on which the packets should be forwarded. For example, a routing table will include forwarding information that relates many different destination Internet protocol (IP) addresses or IP address prefixes to next hop identifiers. It is not uncommon for a forwarding table to have in excess of 100,000 different stored table entries.
In a mesh network architecture, it is likely that there is more than one path that a packet can take to reach its destination. FIG. 1 depicts an example of a mesh network architecture in which there is more than one path that can be used to get packets from a source node to a destination node. For example, packets from source node A 10 can reach destination node C 12 via routers R1 16 and R2 18 and paths 40:60 or via routers R1 and R3 20 and paths 50:90. Likewise, packets from source node A can reach destination node D 14 via routers R1 and R3 and paths 50:70 or via routers R1 and R2 and paths 40:80.
While there may be different possible paths that packets can travel to get from a source node to a destination node in a network, the forwarding information identified during the lookup process only indicates one of the paths. For example, at router R1 16 a lookup for a packet destined for node C 12 will yield forwarding information that identifies only one path (i.e., path 40:60) and a lookup for a packet destined for node D 14 will yield forwarding information that identifies only one path (i.e., path 50:90).
Packet-switched networks are currently being adapted to support traditional telecommunications traffic, such as voice communications. In order for packet-switched networks to support traditional telecommunications traffic, the packet-switched networks must include failure protection mechanisms that ensure a standard of reliability that meets or exceeds the reliability standards that are achieved by circuit-switched networks. For example, in order to preserve the quality of a voice conversation, it is important that a network can recover from a path failure within 50 milliseconds (ms).
One failure protection technique that has been used in packet-based mesh networks involves identifying a secondary, or redundant path, that can be used to re-route traffic in the event of a failure of the primary path. Referring to the example network of FIG. 1, primary and secondary paths may be established between the source node A and the destination nodes. For example, the path 40:60 may be established as the primary path between source node A and destination node C with the path 50:90 being established as the secondary path. Likewise, the path 50:70 may be established as the primary path between source node A and destination node D with the path 40:80 being established as the secondary path. In the event of a failure along path 40:60, the traffic destined for node C can be switched to the secondary path (i.e., path 50:90).
In order to initiate path switching at the lookup stage of packet processing, it is necessary to change the forwarding information that is stored in the lookup table to reflect the desired change in path. In prior art systems, changing the forwarding information is a software-based process that requires re-writing the forwarding information in the lookup table. While re-writing a single table entry or a few table entries in an acceptable time period (i.e., <50 ms) is a trivial task, the task is much more difficult in real-world network nodes, such as switches and routers, which may contain in excess of 100,000 different table entries. For example, if 10,000 table entries need to be updated as a result of a path failure and it takes 10 μs to update each entry, then the time required to update all 10,000 table entries will be 100 ms. In the 100 ms that it takes to update all 10,000 table entries, it is possible that some traffic will be forwarded to the failed path, causing traffic to be lost. Lost traffic will likely result in missing the 50 ms acceptable time limit for failure recovery.
In view of the desire to support traditional telecommunications traffic with packet-based networks, what is needed is a protection switching technique that provides fast protection switching and that can scale to efficiently handle large numbers of different table entries.